\documentclass{article}

\usepackage{standalone}
\standalonetrue
\usepackage{estilo}

\title{CA}
\author{Ricardo Cruz}

\usepackage{graphicx}
\usepackage{amsmath}
\begin{document}

\ifstandalone
\maketitle
\fi

\section{Introduction}

A \gls{CA} is a discrete model, whereby space is discretized as an $n$-dimensional \textit{lattice} composed of \textit{cells}, each of which is in a number of pre-determined, finite \textit{states}, $\sigma \in \Sigma$ (where $\Sigma$ is a set of of states having finite cardinality $|\Sigma|=k$), that change according to a fixed \textit{rule} $\varphi: \Sigma^n \rightarrow \Sigma$. Time itself, $i$, is discrete. At the dawn of the simulation ($i=0$), an initial state is defined for each cell. Usually, the same state is defined for all cells, except for a few. At each iteration ($i$ advances by 1, also known as a tick), the next generation of cells is computed by having each cell independently and synchronously change its state by the rule $\varphi$. For instance, a cell defined as \textit{healthy}, could become \textit{infected} as a result of having infected neighbors. Since the number of states is finite, and transition between states is performed using a fixed rule, each cell may be seen as what is known in computer science by finite state machine, also known as automaton. It should be stressed that the computations themselves are independent, but the rule itself is usually dependent on the states of the cell's neighbors. Most traditional \gls{CA} models are represented in a 2D matrix, whereby the transition rule is based on either its 4 immediate cardinal neighbors, known as von Neumann neighborhood, or the rule is based on all 8 immediate neighbors, known as Moore neighborhood, but many more arrangements exist. \gls{HIV} \gls{CA} models borrow one important property from stochastic cellular automata models by allowing probabilistic transitions.

Because of the performance of its simulations, and in some cases analytical introspection, \gls{CA} model is used in a wide range of fields --- in fact, the name is completely unrelated to \textit{biological} cell, even though here it shall be used in that sense. These models may be seen as the primogenitors and computationally less demanding versions of the \glspl{ABM}. The grid may represent physical space and will be used in that sense, unless otherwise stated, but it may also represent other concepts of space --- such as shape space representing \gls{HIV} mutations \citep{Hershberg2001}. Since each cell is a finite state and is layed out in a grid, they will be rendered visually in different colors.



\section{Santos-Coutinho model}

With over a hundred citations in Google Scholar, \citet{Santos2001} is considered to be the most successful of HIV spatial models, although there are question as to its realistic application \citep{Strain2001}. In HIV spatial dynamics, this and thereby inspired models can be seen as representatives of cell-to-cell transmission within a given organ, most prominently a lymph node (see section \ref{space dynamics}).

Its set of states $\Sigma$ are $\{\text{T},\text{A1},\text{A2},\text{D}\}$, where they represent respectively: healthy, infected stage 1, infected stage 2, and death cell. All starts start with state T, except for a minority fraction $p_\text{HIV}$ that start as A1. The transition function $\varphi$ will be represented here by the diagram in figure \ref{coutinhophi}, as inspired by the diagram at \citet{Shi2008}, and UML state machine diagrams.

\begin{figure}[htb]
\centering
\begin{tikzpicture}
\tikzset{
	status/.style={rectangle, draw=black, text centered, anchor=north, text=black, minimum width=2em, minimum height=2em},
	mstyle/.style={column sep=10em, row sep=2em,nodes={status},font=\bfseries},
	line/.style={draw,thick,-latex},
	row 1 column 1/.style={nodes={fill=green}},
	row 1 column 2/.style={nodes={fill=yellow}},
	row 1 column 3/.style={nodes={fill=red}},
	row 2 column 3/.style={nodes={fill=gray}},
	row 2 column 2/.style={nodes={diamond}},
}
\matrix(m)[matrix of nodes,ampersand replacement=\&,mstyle]{
	T \& A1 \& A2 \\
	  \& {} \&  D \\
};
\draw[line] (m-1-1) -- (m-1-2) node[pos=0.5,above,align=left] {$\#\text{A1} \geq 1$ or\\$\#\text{A2} \geq R$};
\draw[line] (m-1-2) -- (m-1-3) node[pos=0.5,above] {wait $\tau$ ticks};
\draw[line] (m-1-3) -- (m-2-3) node[pos=0.5,right] {wait 1 tick};
\draw[line] (m-2-3) -- (m-2-2) node[pos=0.5,above] {$p_\text{replenished}$};
\draw[line] (m-2-2) -| (m-1-1) node[pos=0.2,above] {$1-p_\text{infected}$};
\draw[line] (m-2-2) -- (m-1-2) node[pos=0.5,left] {$p_\text{infected}$};
\end{tikzpicture}
\caption{Schematic diagram of Coutinho's model. Operator \# represents the number of von Neumann neighborhood with the given state. The colors of the states are the same that will be reused in the following pictures.}
\label{coutinhophi}
\end{figure}

Parameters from the article are:

\noindent
\rowcolors{1}{}{gray!10}
\begin{center}
\begin{tabularx}{0.85\linewidth}{lXll}
\textbf{Parameter} & \textbf{Description} & \textbf{Santos' Values} & \textbf{Our Values} \\\midrule
$L$ & length of the \gls{CA} grid square & 700 & 350 \\
$p_\text{HIV}$ & fraction of initial infected A1 & 0.05 & idem \\
$R$ & $\#\text{A2}$ minimum of contagious neighbors & 4 & idem \\
$\tau$ & waiting time for A1 $\rightarrow$ A2 transition & 4 & idem \\
$p_\text{replenished}$ & probability of death cells to be replaced & 0.99 & idem \\
$p_\text{infected}$ & probability of replenished cells to be infected & $10^{-5}$ & $4 \times 10^{-5}$ \\
\end{tabularx}
\end{center}
\rowcolors{1}{}{}


\begin{figure}[htb]
\centering
\begin{subfigure}[b]{0.20\textwidth}
	\includegraphics[width=\textwidth]{chp3/tick0.png}
	\caption{$i=0$}
\end{subfigure}
\begin{subfigure}[b]{0.20\textwidth}
	\includegraphics[width=\textwidth]{chp3/tick2.png}
	\caption{$i=2$}
\end{subfigure}
\begin{subfigure}[b]{0.20\textwidth}
	\includegraphics[width=\textwidth]{chp3/tick6.png}
	\caption{$i=6$}
\end{subfigure}

\begin{subfigure}[b]{0.20\textwidth}
	\includegraphics[width=\textwidth]{chp3/tick9.png}
	\caption{$i=9$}
\end{subfigure}
\begin{subfigure}[b]{0.20\textwidth}
	\includegraphics[width=\textwidth]{chp3/tick20.png}
	\caption{$i=20$}
\end{subfigure}
\begin{subfigure}[b]{0.20\textwidth}
	\includegraphics[width=\textwidth]{chp3/tick202.png}
	\caption{$i=200$}
\end{subfigure}
\caption{Several snapshots of the model, when using the Moore neighborhood.}
\end{figure}




Rules in traditional \glspl{CA} operate only as a function of its neighbors. Rules from \citet{Santos2001} are less orthodox as they are written also as probabilities and as fixed waiting times. There does not seem to exist obvious means to come up with a faster algorithm than the typical naive implementation of having two cycles over the entire \gls{CA} area; the first to query which rule to apply for each cell, analyzing neighbors prior to making any change, and the second couple of cycles to perform the rule and modify the cell. Complexity is therefore quadratic, i.e. $\mathcal{O}(n^2)$ relatively to \gls{CA} grid square length $L$.

Given that update is synchronous, parallelizing the cycle at each iteration time $i$ is an option, though it is not obvious the system overhead from the parallelization is worth it, definitively not if we are already parallelizing multiple runs of the simulation. Given the lack of computational power, we have reduced $L$, from 700 to 350, and increased $p_\text{infected}$ to reduce the efficacy of the initial immune response and keep the same number of expected virus fixture, so we solve $\text{E(fixture)}=700^2 \times 10^{-5} \land \text{E(fixture)}=350^2 \times p_\text{infected} \Rightarrow p_\text{infected}=4 \times 10^{-5}$. As can be seen later over Figure \ref{moore}, this change speeds up the progress of the disease slightly.

\begin{figure}[htp]
\centering
\includegraphics[scale=0.75]{chp3/time.pdf}
\caption{Time for each simulation run as a function of $L$. Interpolation based on average time from 10 iterations for each $L$.}
\end{figure}

In a follow-up article \citep{Figueiredo2008}, the authors discuss \gls{CA} for robustness under different lattice dispositions, namely triangular as well as 3D and other neighborhood configurations, and perform sensitivity analysis to the parameters. Their conclusion is that their \gls{CA} model is robust, though they present little results and no statistical analysis.



\subsection{Neighborhood configuration}

Several \gls{CA} rules exist for who qualifies as neighbor. The following are two of the most important, while the third is the one used by \citet{Santos2001}, with $r=2$. Their respective formulas are given by:

\begin{enumerate}[label=(\alph*)]
\item $N^{\nu}_{(x_0,y_0)}=\{(x,y): |x-x_0| + |y-y_0| \leq r\}$
\item $N^\text{M}_{(x_0,y_0)}=\{(x,y): |x-x_0| \leq r \lor |y-y_0| \leq r\}$
\item $N^\text{+}_{(x_0,y_0)}=\{(x,y): (|x-x_0| \leq r \land y=y_0) \lor (|y-y_0| \leq r \land x=x_0) \}$
\end{enumerate}

\begin{figure}[htb]
\centering
\begin{subfigure}[t]{0.30\textwidth}
	\begin{tikzpicture}[scale=0.70]
	% r=1
	\fill[fill=black!50] (0,1) rectangle (1,2);
	\fill[fill=black!50] (2,1) rectangle (3,2);
	\fill[fill=black!50] (1,2) rectangle (2,3);
	\fill[fill=black!50] (1,0) rectangle (2,1);
	% r=2
	\fill[fill=black!20] (-1,1) rectangle (0,2);
	\fill[fill=black!20] (3,1) rectangle (4,2);
	\fill[fill=black!20] (1,3) rectangle (2,4);
	\fill[fill=black!20] (1,-1) rectangle (2,0);
	\fill[fill=black!20] (2,2) rectangle (3,3);
	\fill[fill=black!20] (0,0) rectangle (1,1);
	\fill[fill=black!20] (0,2) rectangle (1,3);
	\fill[fill=black!20] (2,0) rectangle (3,1);
	% grid
	\draw[step=1cm,black!40,very thin] (-1.3,-1.3) grid (4.3,4.3);
	\fill[fill=black] (1,1) rectangle (2,2);
	\end{tikzpicture}
	\caption{von Neumann neighborhood, also known as 4-neighborhood}
\end{subfigure}
\begin{subfigure}[t]{0.30\textwidth}
	\begin{tikzpicture}[scale=0.70]
	% r=2
	\fill[fill=black!20] (-1,-1) rectangle (4,4);
	% r=1
	\fill[fill=black!50] (0,0) rectangle (3,3);
	% grid
	\draw[step=1cm,black!40,very thin] (-1.3,-1.3) grid (4.3,4.3);
	\fill[fill=black] (1,1) rectangle (2,2);
	\end{tikzpicture}
	\caption{Moore neighborhood, also known as 8-neighborhood}
\end{subfigure}
\begin{subfigure}[t]{0.30\textwidth}
	\begin{tikzpicture}[scale=0.70]
	% r=1
	\fill[fill=black!50] (0,1) rectangle (1,2);
	\fill[fill=black!50] (2,1) rectangle (3,2);
	\fill[fill=black!50] (1,2) rectangle (2,3);
	\fill[fill=black!50] (1,0) rectangle (2,1);
	% r=2
	\fill[fill=black!20] (-1,1) rectangle (0,2);
	\fill[fill=black!20] (3,1) rectangle (4,2);
	\fill[fill=black!20] (1,3) rectangle (2,4);
	\fill[fill=black!20] (1,-1) rectangle (2,0);
	% grid
	\draw[step=1cm,black!40,very thin] (-1.3,-1.3) grid (4.3,4.3);
	\fill[fill=black] (1,1) rectangle (2,2);
	\end{tikzpicture}
	\caption{Our cross neighborhood}
\end{subfigure}
\label{neighborhoods}
\caption{Contrasting neighborhood configurations. In dark gray, $r=1$. In light gray, $r=2$.}
\end{figure}

For this kind of models, only general qualitatively analysis make sense, since it is yet impossible to calibrate the model with real data. In fact, it is unknown the modus operandi behind HIV cell-to-cell transmission; the idea behind these models is exactly proposing plausible hypothesis for the phenomenon. Here we contrast \citet{Santos2001} neighborhood configuration (which is a Moore of $r=1$) against our own Cross neighborhood (of $r=2$), see Figure \ref{neighborhoods}. The reason we compare these two is because both have 8 neighbors, so the logic behind rule ``$\#\text{A1} \geq R$'' remains intact. Our cross neighborhood configuration slightly speeds up disease progression during the chronic phase, but interestingly the results are qualitatively similar. We had already modify $L$, so such as in \citep{Figueiredo2008}, we find the the authors discuss \gls{CA} for robustness under different lattice dispositions, namely triangular as well as 3D and other neighborhood configurations, and perform sensitivity analysis to the parameters. Their conclusion is that their \gls{CA} model is robust, though they present little results and no statistical analysis.


\begin{figure}[htb]
\centering
\begin{subfigure}[b]{0.70\textwidth}
	\includegraphics[width=\textwidth]{chp3/moore.pdf}
	\caption{General disease dynamics; acute and chronic phases are in different temporal scales}
\end{subfigure}
\begin{subfigure}[b]{0.28\textwidth}
	\includegraphics[width=\textwidth]{chp3/moore-closeup.png}
	\caption{Wave dynamics}
\end{subfigure}
\label{moore}
\caption{Moore neighborhood ($r=1$); the disease spreads as expected from the paper.}
\end{figure}

\begin{figure}[htb]
\centering
\begin{subfigure}[b]{0.70\textwidth}
	\includegraphics[width=\textwidth]{chp3/cross.pdf}
	\caption{General disease dynamics; acute and chronic phases are in different temporal scales}
\end{subfigure}
\begin{subfigure}[b]{0.28\textwidth}
	\includegraphics[width=\textwidth]{chp3/cross-closeup.png}
	\caption{Wave dynamics}
\end{subfigure}
\label{cross}
\caption{Moore neighborhood ($r=1$); the disease spreads as expected from the paper.}
\end{figure}






\subsection{Variance Reduction}



\section{Incorporating Treatment}

In a latter article \citep{Gonzalez2013}, the authors incorporated reverse transcriptase inhibitor, protease inhibitor, and combined treatment into the model.

\begin{figure}[htb]
\centering
\begin{tikzpicture}
\tikzset{
	status/.style={rectangle, draw=black, text centered, anchor=north, text=black, minimum width=2em, minimum height=2em},
	mstyle/.style={column sep=6em, row sep=4em,nodes={status},font=\bfseries},
	line/.style={draw,thick,-latex},
	line2/.style={draw,thick,latex-latex},
	row 1 column 2/.style={nodes={fill=green}},
	row 1 column 3/.style={nodes={fill=yellow}},
	row 1 column 4/.style={nodes={fill=red}},
	row 2 column 4/.style={nodes={fill=gray}},
	row 2 column 3/.style={nodes={diamond}},
}
\matrix(m)[matrix of nodes,ampersand replacement=\&,mstyle]{
	T\textsubscript{P} \& T \& A1 \& A2 \\
	T\textsubscript{RTP}  \& T\textsubscript{RT} \& {} \&  D \\
};
\draw[line] (m-1-2) -- (m-1-3) node[pos=0.5,above,align=left] {$\#\text{A1} \geq R$ or\\$\#\text{A2} \geq 1$};
\draw[line] (m-1-3) -- (m-1-4) node[pos=0.5,above] {wait $\tau$ ticks};
\draw[line] (m-1-4) -- (m-2-4) node[pos=0.5,right] {wait 1 tick};
\draw[line] (m-2-4) -- (m-2-3) node[pos=0.5,above] {$p_\text{replenished}$};
\draw[line] (m-2-3) -- (m-1-2);% node[pos=0.2,above] {$1-p_\text{infected}$};
\draw[line] (m-2-3) -- (m-1-3) node[pos=0.5,right] {$p_\text{infected}$};
\draw[line2] (m-1-2) -- (m-1-1);
\draw[line2] (m-1-2) -- (m-2-2);
\draw[line] (m-1-1) -- (m-2-1);
\draw[line] (m-2-2) -- (m-2-1);
\draw[line] (m-2-1) -- (m-1-2);
\end{tikzpicture}
\caption{Schematic diagram of Coutinho's model. Operator \# represents the number of von Neumann neighborhood with the given state. The colors of the states are the same that will be reused in the following pictures.}
\label{coutinho2phi}
\end{figure}







\section{Shape space dynamics}

Rather than studying spatial dynamics, \citet{Hershberg2001} studied ``shape space'' dynamics, describing shape space using a \gls{CA}, whereby each space of the grid represents a different strain.


\section{Cellular Potts Model}

The Cellular Potts Model (CPM) can be seen as a generalization of the \gls{CA}. Originally by \citet{Graner1992}, CPM is an extension of the large-Q Potts Model, which is in turn a generalization of the Ising-spin model. It has been successful used in computational modeling to various phenomena such as cells, foam, and fluid flow. Here, a biological cell may occupy several \gls{CA} cells, and thus volume and shape is realized and such phenomena as cell growth and division, and as elongation and movement, can be more accurately simulated. From simple rules, sophisticated behavior can be realized such as adhesion of cell to its surrounding matrix. When form is of no concern, an \glspl{ABM} such as a particle simulator may be computationally preferable. The following picture, contrasts a \gls{CA} against a Potts model; the Potts model is functionally richer, but computationally slower in that a biological cell is composed by several cells of the lattice.

Knowledge of HIV is not detailed enough to come to this level of resolution, but we feel this model is the next step in HIV cell-to-cell transmission modeling, and given their preeminence in biological computing, we felt a brief description was in order.

\begin{figure}[htb]
\centering
\begin{subfigure}[b]{0.20\textwidth}
	\begin{tikzpicture}[scale=0.70]
	\draw[step=1cm,lightgray,very thin] (-0.3,-0.3) grid (3.3,2.3);
	\filldraw[fill=blue!40,draw=darkgray] (2,0) rectangle (3,1);
	\filldraw[fill=red!40,draw=darkgray] (0,1) rectangle (1,2);
	\end{tikzpicture}
	\caption{\gls{CA} model}
\end{subfigure}
\begin{subfigure}[b]{0.20\textwidth}
	\begin{tikzpicture}[scale=0.70]
	\fill[blue!40] (4,1) rectangle (6,3);
	\fill[blue!40] (3,1) rectangle (4,2);
	\fill[blue!40] (4,0) rectangle (5,1);
	\fill[red!40] (0,3) rectangle (2,4);
	\fill[red!40] (1,4) rectangle (2,5);
	\draw[step=1cm,lightgray,very thin] (-0.3,-0.3) grid (6.3,5.3);
	\draw[darkgray] (4,2) -- (4,3) -- (6,3) -- (6,1) -- (5,1) -- (5,0) -- (4,0) -- (4,1) -- (3,1) -- (3,2) -- (4,2);
	\draw[darkgray] (0,3) -- (2,3) -- (2,5) -- (1,5) -- (1,4) -- (0,4) -- (0,3);
	\end{tikzpicture}
	\caption{Cellular Potts model}
\end{subfigure}
\caption{Models representing the same two cells, but with different details. Unlike in the Cellular Automaton model, where each cell represents an agent. In the Cellular Potts model each cell is assigned the identifier of which agent is placed there, and this agent (be it a biologic cell or a molecule) can encompass several of these cells and shape can be modeled.}
\label{fig:CPM}
\end{figure}

In this model, each agent is offered an individual identifier, $\sigma(\mathbf{x})$ (can be an integer, or a color, say ``blue'' and ``pink'' in Figure \ref{CPM}). Several cells in the lattice may encompass a single agent, in which case they are described by its identifier. For computational efficiency, time here is advanced asynchronously, in which case a random cell $\mathbf{x}$ is chosen and there is an attempt to copy it to a randomly chosen neighbor, if they are not the same $\sigma(\mathbf{x}) \neq \sigma(\mathbf{x'})$; whether the attempt is successful or not depends on whether, after copy, the energy of the system would be lower, otherwise it depends on a probability based on Boltzmann distribution. To calculate the energy at any given point, the Hamiltonian equation has the following form:

\begin{align*}
H &= \sum_{\mathbf{x},\mathbf{x'} \text{neighbors}} J(\tau(\sigma(\mathbf{x})),\tau(\sigma(\mathbf{x'})))(1-\delta(\sigma(\mathbf{x}),\sigma(\mathbf{x'})) \\
&+ \sum_{\mathbf{x}} \lambda_\text{volume} [V(\sigma(\mathbf{x})) - V_\text{target}(\sigma(\mathbf{x}))]^2 \\
&+ \sum_{\mathbf{x}} \lambda_\text{surface} [S(\sigma(\mathbf{x})) - S_\text{target}(\sigma(\mathbf{x}))]^2
\end{align*}

\noindent
where for each cell of the lattice $\mathbf{x}$ and its neighbors $\mathbf{x'}$, $\lambda_\text{volume}$ and $\lambda_\text{surface}$is are volume and surface constrains, respectively, $J$ is the boundary coefficient given by two biological cell types, and $\tau$ is the biological type associated to the cell in the lattice, and $\delta$ is the Kronecker delta. This function is thus calculated twice at each copy attempt when testing for motility, penalizing 

For chemotaxis, usually the method from \citet{Savill1997} is used whereby a grid of the same size as the lattice of cells is created whereby each number of this grid represents of the liquid. Diffusion can happen independently of the overlying lattice. The energy provided by the chemotaxis is then subtracted from the Hamilton.



%%% END

\ifstandalone
\printglossary
\printbibliography
\fi

\end{document}
